//计数排序，O（n）https://www.cnblogs.com/developerY/p/3166462.html
public class CountSort {

    private static int[] countSort(int[] array,int k)
    {
        int[] C=new int[k+1];//构造C数组
        int length=array.length,sum=0;//获取A数组大小用于构造B数组
        int[] B=new int[length];//构造B数组
        for(int i=0;i<length;i++)
        {
            C[array[i]]+=1;// 统计A中各元素个数，存入C数组
        }
        for(int i=0;i<k+1;i++)//修改C数组
        {
            sum+=C[i];
            C[i]=sum;
        }
        for(int i=length-1;i>=0;i--)//遍历A数组，构造B数组
        {

            B[C[array[i]]-1]=array[i];//将A中该元素放到排序后数组B中指定的位置
            C[array[i]]--;//将C中该元素-1，方便存放下一个同样大小的元素

        }
        return B;
    }

    public static void main(String[] args)
    {
        int[] A=new int[]{2,5,3,0,2,3,0,3};
        int[] B=countSort(A, 5);
        for(int i=0;i<A.length;i++)
        {
            System.out.println((i+1)+"th:"+B[i]);
        }
    }

}
